public class main {

    public static void main(String[] args) {
        int[] prices = {};
        System.out.println(maxProfit(prices, 6806));
//        int[] prices = {1, 3, 2, 8, 4, 9};
//        maxProfit(prices,2);
    }

//    public static int maxProfit(int[] prices, int fee) {
//        Integer maxAmount = null;
//        Integer[][] priceArr = new Integer[prices.length+1][prices.length+1];
//        for(int i=1;i<prices.length+1;i++){
//            priceArr[i][0] = prices[i-1];
//        }
//        for(int j=1;j<prices.length+1;j++){
//            priceArr[0][j] = prices[j-1];
//        }
//
//        for(int j=1;j<prices.length+1;j++){
//            for(int i=1;i<prices.length+1;i++){
//                if(i<=j){
//                    int basicPrice = priceArr[0][j]-priceArr[i][0]-fee;
//                    if(basicPrice<=0){
//                        continue;
//                    }
//                    Integer maxPrice = null;
//                    for(int ki=1;ki<=i;ki++){
//                        for(int kj=1;kj<=i;kj++){
//                            if(null==maxPrice||(null!=priceArr[ki][kj]&&maxPrice<=priceArr[ki][kj])){
//                                maxPrice = priceArr[ki][kj];
//                            }
//                        }
//                    }
//                    priceArr[i][j]=(basicPrice<=0?0:basicPrice)+(maxPrice==null||maxPrice<=0?0:maxPrice);
////                    printArr(priceArr);
//                    if(null==maxAmount||(priceArr[i][j]>=maxAmount)){
//                        maxAmount = priceArr[i][j];
//                    }
//                }else{
//                    break;
//                }
//            }
//        }
//        return maxAmount;
//    }


//    public static int maxProfit(int[] prices, int fee) {
//        Integer maxAmount = null;
//        int[] maxArr = new int[prices.length];
//        Integer[][] priceArr = new Integer[prices.length + 1][prices.length + 1];
//        for (int i = 1; i < prices.length + 1; i++) {
//            priceArr[i][0] = prices[i - 1];
//        }
//        for (int j = 1; j < prices.length + 1; j++) {
//            priceArr[0][j] = prices[j - 1];
//        }
//
//        for (int j = 1; j < prices.length + 1; j++) {
//            for (int i = 1; i < prices.length + 1; i++) {
//                if (i <= j) {
//                    int basicPrice = priceArr[0][j] - priceArr[i][0] - fee;
////                    if(basicPrice<=0){
////                        continue;
////                    }
////                    for(int ki=1;ki<=i;ki++){
////                        for(int kj=1;kj<=i;kj++){
////                            if(null==maxPrice||(null!=priceArr[ki][kj]&&maxPrice<=priceArr[ki][kj])){
////                                maxPrice = priceArr[ki][kj];
////                            }
////                        }
////                    }
//                    priceArr[i][j] = basicPrice + maxArr[i - 1];
//                    if (priceArr[i][j] > maxArr[max(i, j) - 1]) {
//                        maxArr[max(i, j) - 1] = priceArr[i][j];
//                    } else if (max(i, j) - 2 >= 0 && maxArr[max(i, j) - 2] >= maxArr[max(i, j) - 1]) {
//                        maxArr[max(i, j) - 1] = maxArr[max(i, j) - 2];
//                    }
////                    printArr(priceArr);
//                    if (null == maxAmount || (priceArr[i][j] >= maxAmount)) {
//                        maxAmount = priceArr[i][j];
//                    }
//                } else {
//                    break;
//                }
//            }
//        }
//        return maxAmount <= 0 ? 0 : maxAmount;
//    }

    public static int maxProfit(int[] prices, int fee) {
        int cash = 0, hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            cash = Math.max(cash, hold + prices[i] - fee);
            hold = Math.max(hold, cash - prices[i]);
        }
        return cash;

    }

    static int max(int i, int j) {
        return i > j ? i : j;
    }

    static void printArr(Integer[][] arr) {
        for (int j = 0; j < arr.length; j++) {
            for (int i = 0; i < arr.length; i++) {
                String id = String.format("  %06d", arr[i][j]);
                System.out.print(id);
            }
            System.out.print("\n");
        }
    }
}
